README.md

155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2. 

Solutions (Rust)

1. Two Stacks

structMinStack{data:Vec<i32>,min:Vec<i32>,}/** * `&self` means the method takes an immutable reference. * If you need a mutable reference, change it to `&mut self` instead. */implMinStack{/** initialize your data structure here. */fnnew() -> Self{Self{data:Vec::new(),min:Vec::new(),}}fnpush(&mutself,x:i32){ifself.min.len() == 0 || x <= self.get_min(){self.min.push(x);}self.data.push(x);}fnpop(&mutself){ifself.top() == self.get_min(){self.min.pop();}self.data.pop();}fntop(&self) -> i32{*self.data.last().unwrap()}fnget_min(&self) -> i32{*self.min.last().unwrap()}}/** * Your MinStack object will be instantiated and called as such: * let obj = MinStack::new(); * obj.push(x); * obj.pop(); * let ret_3: i32 = obj.top(); * let ret_4: i32 = obj.get_min(); */

2. One Stack

structMinStack{data:Vec<(i32,i32)>,}/** * `&self` means the method takes an immutable reference. * If you need a mutable reference, change it to `&mut self` instead. */implMinStack{/** initialize your data structure here. */fnnew() -> Self{Self{data:Vec::new(),}}fnpush(&mutself,x:i32){ifself.data.len() == 0 || x <= self.get_min(){self.data.push((x, x));}else{self.data.push((x,self.get_min()));}}fnpop(&mutself){self.data.pop();}fntop(&self) -> i32{self.data.last().unwrap().0}fnget_min(&self) -> i32{self.data.last().unwrap().1}}/** * Your MinStack object will be instantiated and called as such: * let obj = MinStack::new(); * obj.push(x); * obj.pop(); * let ret_3: i32 = obj.top(); * let ret_4: i32 = obj.get_min(); */